[Coding033] LeetCode 25

Reverse Nodes in k-Group

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

1. 递归程序写的很巧妙，需要多看看类似的程序，培养自己的递归思维；

2. 头插法的新写法，用到了prev这个指针，感觉很新奇；

3. 在解法2中，平铺直叙的叙述下，控制大循环的cnt和内循环的k很值得思考。这个逻辑一开始在写的时候还是比较紊乱的。后来就厘清了！

题目：25. Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

xxxxxxxxxx
2
1
Input: head = [1,2,3,4,5], k = 2
2
Output: [2,1,4,3,5]

Example 2:

xxxxxxxxxx
2
1
Input: head = [1,2,3,4,5], k = 3
2
Output: [3,2,1,4,5]

Constraints:

• The number of nodes in the list is n.

• 1 <= k <= n <= 5000

• 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

代码1（配 · 手绘过程图）

xxxxxxxxxx
47
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode reverseKGroup(ListNode head, int k) {
13
        ListNode node = head;
14
        if (node == null) return node;
15

16
        for (int i = 0; i < k - 1; i++)
17
        {
18
            node = node.next;
19
            if (node == null) return head;  // 不够k个，不翻转，直接返回head
20
        }
21

22
        node.next = reverseKGroup(node.next, k);
23
        return reverseLinkedList(head, node.next);
24
    }
25

26
    private ListNode reverseLinkedList(ListNode head, ListNode tail)
27
    {
28
        ListNode p = head;
29
        ListNode prev = null;
30

31
        while (p != tail)
32
        {
33
            ListNode tmp = p.next;  // 防止链表断裂
34

35
            // 每次来的新节点放在之前节点的最前面
36
            p.next = prev;
37
            prev = p;
38

39
            p = tmp;   // 处理下一个节点
40
        }
41

42
        // head自始至终都没变过，指向的是第一个节点（但此时第一个节点已经变成最后一个）
43
        head.next = tail;  // 防止链表断裂，把tail接起来
44

45
        return prev;
46
    }
47
}

代码解读 | 评价

• 递归程序，每次处理k个，然后依次把处理好的k个连接起来。

  • 目前对其中的reverseKGroup()这个函数无法特别共鸣，但是可以知道，这个函数每次的head和node.next包裹的内容就是k个待翻转的链表段的（头 和 尾）。

  • 一定要多写写这些程序，才能深刻体会到递归的魅力！

• 值得借鉴的思想

  • prev这个指针很巧妙，在翻转链表的时候，每次都把新节点放在prev的前面（通过代码p.next = prev;实现），然后再把新的头结点看成prev（通过代码prev = p;实现）；

  • 这个比起头插法，显得更简洁明了。（适用于没有dummy的情况）。

复杂度分析

这个挺快的。

代码2（配 · 手绘过程图）

xxxxxxxxxx
56
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode reverseKGroup(ListNode head, int k) {
13
        if (head == null)
14
            return null;
15

16
        ListNode dummy = new ListNode(0);
17
        dummy.next = head;
18

19
        ListNode cp = head;
20
        int cnt = 0;
21
        while (cp != null)
22
        {
23
            cnt++;
24
            cp = cp.next;
25
        }
26
        cnt = cnt / k;  // 看看总共会翻转几轮（7个数，3个一翻转的话，就是2轮，最后一个不翻转）
27

28
        if (cnt == 0)
29
            return head;  // 少于k个，就不翻转了
30

31
        ListNode cur = dummy;
32
        int t = k;  // t每轮翻转的时候递减
33

34
        while (cnt != 0)
35
        {
36
            cnt--;  // 翻转一轮，减1次；
37
            t--;
38

39
            ListNode p = cur.next;
40
            while (t != 0 && p.next != null)
41
            {
42
                ListNode q = p.next;
43
                p.next = q.next;  // 防止链表断裂
44
                q.next = cur.next;  // 新节点安装（装尾巴）
45
                cur.next = q;  // 新节点安装（装头部）
46

47
                t--;  // 总共要处理k个节点，处理一次减1个
48
            }
49

50
            cur = p;  // 新一轮的head
51
            t = k;  // 新一轮的计数
52
        }
53

54
        return dummy.next;
55
    }
56
}

代码解读 | 评价

• 这段代码相对于上一个用了递归思想的代码，就是平铺直叙的书写方式。

• 需要特别注意

  • cnt和k的关系

    • cnt是大循环，k是每次大循环中要翻转的k个元素；

      e.g., 假如说对于7个节点的链表，如果每波翻转3个节点，则要翻转2波；

      即：k = 3, cnt = 2

  • 程序的核心控制就是cnt和k，但是k每次会更新；

复杂度分析

这个比较慢。